#pragma once
#include <unordered_map>
#include <list>

using namespace std;

template<typename K, typename V, size_t S>
class LRUCache
{
public:
	class Node
	{
	public:
		K key;
		V val;
	};
public:
	void Add(K key, V val)
	{
		auto it = ht.find(key);
		if (it != ht.end())
		{
			it->second->val = val;
			_Active(it->second);
		}
		else
		{
			Node* pNode = new Node{key, val};

			ht[key] = pNode;
			lru.push_front(pNode);

			_KickOut();
		}
	}

	V* Get(K key)
	{
		auto it = ht.find(key);
		if (it == ht.end())
		{
			return nullptr;
		}
		_Active(it->second);
		return &(it->second->val);
	}

	bool Delete(K key)
	{
		auto it = ht.find(key);
		if (it == ht.end())
		{
			return false;
		}
		delete it->second;
		lru.remove(it->second);
		ht.erase(it);
		return true;
	}

private:
	void _KickOut()
	{
		if (lru.size() <= S)
		{
			return;
		}
		auto node = lru.back();
		ht.erase(node->key);
		lru.pop_back();
	}

	void _Active(Node* node)
	{
		lru.remove(node);
		lru.push_front(node);
	}

private:
	list<Node*> lru;
	unordered_map<K, Node*> ht;
};